package org.mango.basic;

import java.util.Scanner;

/**
 * 
 * @author 戴礼明
 *日期： 2016-4-21
 *content：分治算法
 *找硬币问题(较轻的为假)
 */
public class DivideAndConquer {
  
	
	    public static int caculate(int coin[],int low,int high){
	    	
	    	int sum1,sum2,sum3;
	    	sum1=sum2=sum3=0;
	    	
	    	if(low+1==high){
	    		if(coin[low]<coin[high]){
    				System.out.println("low+1 ");
	    			return low+1; 
	    			}
	    			else{ 
	    			System.out.println("high+1");
	    				return high+1;}
	    	}
	    		 
	    		
	    		if((high-low+1)%2==0){//偶数
	    			for(int i=0;i<(high-low+1)/2;i++){
	    				 sum1=sum1+coin[i];
	    			 }
	    			
	    			for(int i=low+(high-low)/2+1;i>low;i--){
	    			   sum2=sum2+coin[i];	   
	    			}
	    			
	    			if(sum1>sum2){
	    				return caculate(coin, low+(high-low)/2+1, high);
	    			}else if(sum2>sum1){
	    				 return caculate(coin, low, high-(high-low)/2);
	    			}
	    		}else{
	    			
	    			for(int i=low;i<=low+(high-low)/2-1;i++){
	    				 sum1=sum1+coin[i];
	    			}
	    			
	    			for(int i=low+(high-low)/2+1;i<=high;i++){
	    				  sum2=sum2+coin[i];
	    			}
	    			
	    			sum3=coin[(high-low)/2+low];
	    			
	    			if(sum1>sum2){
	    				return caculate(coin, low+(high-low)/2+1, high);
	    			}else if(sum2>sum1){
	    				return caculate(coin, low, high-(high-low)/2);
	    			}
	    			if(sum1+sum3==sum2+sum3){
	    				System.out.println("奇数：sum1+sum3==sum2+sum3");
	    				return low+(high-low)/2+1;
	    			 }
	    		}
				return 0;
	    }
	    
	    public static void main(String[] args) {
	    	int[] coin=new int[100];
	    	 int postion;
	    	 System.out.println("请输入硬币的个数");
	    	 Scanner s=new Scanner(System.in);
	    	  int n=s.nextInt();
	    	  for(int i=0;i<n;i++){
	    		  System.out.println("请输入硬币的真假");
	    		    coin[i]=s.nextInt();
	    	  }
			  postion=caculate(coin, 0,n-1);
			  System.out.println("在"+n+"个硬币中，第"+postion+"为假！");
		}
	    
	    }
	
	
